package 算法基础模板.chapter_02;

/**
 * <blockquote><pre>{@code
 *  s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
 *  求模式串的Next数组：
 *  for(int i=2,j=0;i<=m;i++)
 *  {
 *      while(j&&p[i]!=p[j+1]) j=ne[j];
 *      if(p[i]==p[j+1]) j++;
 *      ne[i]=j;
 *  }
 *
 *   // 匹配
 *  for(int i=1,j=0;i<=n;i++)
 *  {
 *      while(j&&s[i]!=p[j+1])j=ne[j];
 *      if(s[i]==p[j+1])j++;
 *      if(j==m)
 *      {
 *          j=ne[j];
 *           // 匹配成功后的逻辑
 *      }
 *  }
 *
 *  作者：yxc
 *  链接：https://www.acwing.com/blog/content/404/
 *  来源：AcWing
 *  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * }
 * @author Summerday
 */
public class KMP {

    public int bl_strStr(String txt, String pat) {
        int m = pat.length(), n = txt.length();
        if (m == 0) return 0;
        for (int i = 0; i <= n - m; i++) {
            for (int j = 0; j < m; j++) {
                // 暴力做法,一旦不匹配,i指针就需要回退
                if (pat.charAt(j) != txt.charAt(i + j)) break;
                if (j == m - 1) return i;
            }
        }
        return -1;
    }

    // 最长公共前后缀
    // https://leetcode-cn.com/problems/implement-strstr/solution/zhe-ke-neng-shi-quan-wang-zui-xi-de-kmp-8zl57/
    public int kmp_strStr(String txt, String pat) {
        int m = pat.length(), n = txt.length();
        if (m == 0) return 0;
        int[] next = new int[m + 1];

        // 构建next数组,之和pat有关  next[1] = 0;
        for (int i = 2, j = 0; i <= m; i++) {
            while (j > 0 && pat.charAt(i - 1) != pat.charAt(j))
                j = next[j];
            if (pat.charAt(i - 1) == pat.charAt(j))
                j++;
            next[i] = j;
        }

        // i指针永远不会回退, 而是借助next数组 每次不匹配时将 pat移到正确的位置继续匹配
        for (int i = 1, j = 0; i <= n; i++) {
            while (j > 0 && txt.charAt(i - 1) != pat.charAt(j))
                j = next[j];
            if (txt.charAt(i - 1) == pat.charAt(j))
                j++;
            // 模式串走完,表示匹配成功, (i - 1) - m + 1
            if (j == m)
                return i - m;
        }
        return -1;
    }

    public int kmp_0_strStr(char[] txt, char[] pat) {
        int m = pat.length, n = txt.length;
        if (m == 0) return 0;
        int[] next = new int[m];
        next[0] = -1;
        for (int i = 1, k = -1; i < m; i++) {
            //我们此时知道了 [0,i-1]的最长前后缀，但是k+1的指向的值和i不相同时，我们则需要回溯
            //因为 next[k]就时用来记录子串的最长公共前后缀的尾坐标（即长度）
            //就要找 k+1前一个元素在next数组里的值,即next[k+1]
            while (k != -1 && pat[k + 1] != pat[i]) {
                k = next[k];
            }
            // 相同情况，就是 k的下一位，和 i 相同时，此时我们已经知道 [0,i-1]的最长前后缀
            //然后 k - 1 又和 i 相同，最长前后缀加1，即可
            if (pat[k + 1] == pat[i]) {
                ++k;
            }
            next[i] = k;
        }

        for (int i = 0, j = 0; i < n; i++) {
            //发现不匹配的字符，然后根据 next 数组移动指针，移动到最大公共前后缀的，
            //前缀的后一位,和咱们移动模式串的含义相同
            while (j > 0 && txt[i] != pat[j]) {
                j = next[j - 1] + 1;
                //超出长度时，可以直接返回不存在
                if (m - j + i > n) {
                    return -1;
                }
            }
            //如果相同就将指针同时后移一下，比较下个字符
            if (txt[i] == pat[j]) {
                ++j;
            }
            //遍历完整个模式串，返回模式串的起点下标
            if (j == m) {
                return i - m + 1;
            }

        }
        return -1;
    }
}
